﻿// Learn more about F# at http://fsharp.net
// See the 'F# Tutorial' project for more help.

// From the goodness of Jon Harrup's heart. 

module SimpleFFT

open System.Numerics

let fft (zs: _ []) =
  let rec loop n offset stride =
    if n < 2 then Array.init n (fun i -> zs.[offset+i*stride]) else
      let e = loop (n/2) offset (2*stride)
      let o = loop (n/2) (offset+stride) (2*stride)
      let a = Array.create n Complex.Zero
      let f k k' =
        let t = 2. * System.Math.PI * float k / float n
        a.[k] <- e.[k'] + Complex(cos t, sin t) * o.[k']
      for k=0 to n/2 - 1 do
        f k k
      for k=n/2 to n-1 do
        f k (k - n/2)
      a
  loop zs.Length 0 1

[<EntryPoint>]
let main argv = 
    let zs = Array.init 2097152 (fun i -> Complex(1.0 / (1.0 + float i), 0.0))
    let r = fft zs
    0 // return an integer exit code
